#pragma once
#include <iostream>
#include <vector>

using namespace std;

enum status
{
    EMPTY = 0,
    EXIST,
    DELETE,
};

template<class K, class V>
struct hash_data
{
    pair<K, V> _kv;
    status _st;

    hash_data<K, V>() : _st(EMPTY)
    {}
    hash_data<K, V>(const pair<K, V>& kv) : _kv(kv), _st(EMPTY)
    {}
};

template<class K, class V>
class hash_table
{
public:
    hash_table<K, V>(const size_t n = 10)
    {
        //_table.resize(n);
    }

public:
    bool insert(const pair<K, V>& kv)
    {
        if (_table.size() == 0 || _size * 10 / _table.size() >= 7)
        {
            size_t new_size = _size == 0 ? 10 : _table.size() * 2;
            hash_table<K, V> new_hash;
            new_hash._table.resize(new_size);

            for (auto& data : _table)
            {
                if (data._st == EXIST)
                    new_hash.insert(data._kv);
            }

            _table.swap(new_hash._table);
        }

        size_t hashi = kv.first % _table.size();

        size_t i = 1;
        size_t idx = hashi;
        while (_table[idx]._st == EXIST)
        {
            if (_table[idx]._kv.first == kv.first)
                return false;

            idx += i;
            idx %= _table.size();
        }

        _table[idx]._kv = kv;
        _table[idx]._st = EXIST;
        ++_size;
        return true;
    }

    hash_data<K, V>* find(const K& key)
    {
        if (_table.empty())
        {
            return nullptr;
        }

        size_t hashi = key % _table.size();
        size_t idx = hashi;
        size_t i = 1;

        while (_table[idx]._st != EMPTY)
        {
            if (_table[idx]._st == EXIST && _table[idx]._kv.first == key)
                return &_table[idx];
            idx += i;

            if (idx == hashi) // all data found
            {
                break;
            }
        }

        return nullptr;
    }

    bool erase(const K& key)
    {
        hash_data<K, V>* pos = find(key);
        if (pos)
        {
            pos->_st = DELETE;
            --_size;
            return true;
        }
        else
        {
            return false;
        }
    }

private:
    vector<hash_data<K, V>> _table;
    size_t _size = 0;
};